#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int mod = 1e9 + 7;
    int number(int n) {
        int ret = 1;
        while (n--) ret = (ret + ret) % mod;
        return ret;
    }
    int sumOfPower(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(k + 1);
        for (int i = 0; i < n; i++) {
            for (int j = k; j > 0; j--) {
                dp[j] = (dp[j] + dp[j]) % mod;
                if (nums[i] == j) dp[j] = (dp[j] + number(i)) % mod;
                else if (nums[i] < j) dp[j] = (dp[j] + dp[j - nums[i]]) % mod;
            }
        }
        return dp[k];
    }
};

class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        int n = nums.size(), mod = 1e9 + 7;;
        vector<long long> dp(k + 1);
        dp[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = k; j >= 0; j--) dp[j] = (2 * dp[j] + (j >= nums[i] ? dp[j - nums[i]] : 0)) % mod;
        return dp[k];
    }
};